package week_four;

import java.util.*;

//TODO:BFS解法，独立未完成，需要重新梳理。
public class LongestIncreasingPathInMatrix_BFS_329 {
    private int m, n;
    private int[][] inDeg;
    private Map<Integer, List<int[]>> edges;
    private int[] dx = {0, 1, 0, -1};
    private int[] dy = {1, 0, -1, 0};

    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        inDeg = new int[m][n];
        edges = new HashMap<>();
        int res = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //add edges
                for (int x = 0; x < 4; x++) {
                    int nextx = i + dx[x];
                    int nexty = j + dy[x];
                    if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
                        if (matrix[i][j] > matrix[nextx][nexty]) {
                            List<int[]> out = edges.getOrDefault(nextx * 1000 + nexty, new ArrayList<>());
                            out.add(new int[]{i, j});
                            edges.put(nextx * 1000 + nexty, out);
                            inDeg[i][j]++;
                        }
                    }
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (inDeg[i][j] == 0) {
                    res = Math.max(res, bfs(matrix, i, j));
                }
            }
        }
        return res;
    }

    private int bfs(int[][] matrix, int x, int y) {
         System.out.println("from x and y: "+ x + " "+y);
        Queue<int[]> q = new LinkedList<>();
        //{i,j,depth}
        int maxDep = 0;
        q.offer(new int[]{x, y, 1});

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int currx = curr[0];
            int curry = curr[1];
            maxDep = curr[2];
             System.out.print(matrix[currx][curry]);
            // maxDep = Math.max(maxDep, depth);
            List<int[]> out = edges.get(currx * 1000 + curry);
            if (out != null) {
                for (int[] big : out) {
                    int nx = big[0];
                    int ny = big[1];
                    inDeg[nx][ny]--;
                     if(inDeg[nx][ny]==0){
                        q.offer(new int[]{nx, ny, maxDep + 1});
                     }
                }
            }
        }

        return maxDep;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {19, 18, 17, 16, 15, 14, 13, 12, 11, 10}, {20, 21, 22, 23, 24, 25, 26, 27, 28, 29}, {39, 38, 37, 36, 35, 34, 33, 32, 31, 30}, {40, 41, 42, 43, 44, 45, 46, 47, 48, 49}, {59, 58, 57, 56, 55, 54, 53, 52, 51, 50}, {60, 61, 62, 63, 64, 65, 66, 67, 68, 69}, {79, 78, 77, 76, 75, 74, 73, 72, 71, 70}, {80, 81, 82, 83, 84, 85, 86, 87, 88, 89}, {99, 98, 97, 96, 95, 94, 93, 92, 91, 90}, {100, 101, 102, 103, 104, 105, 106, 107, 108, 109}, {119, 118, 117, 116, 115, 114, 113, 112, 111, 110}, {120, 121, 122, 123, 124, 125, 126, 127, 128, 129}, {139, 138, 137, 136, 135, 134, 133, 132, 131, 130}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
        int i = new LongestIncreasingPathInMatrix_BFS_329().longestIncreasingPath(matrix);
        System.out.println(i);
    }
}
